In the utilization of concurrent programming languages, it is often desirable to be able to convert a concurrent specification of a program into an equivalent sequential specification (for efficiency reasons, in order to be run on a sequential processor).
For example, real-time embedded computer systems (or more generally, reactive real-time systems) are often most effectively specified, from a functional level, in terms of a concurrent programming language. In terms of providing an executable for the embedded system, which can be executed with greater efficiency (in terms of both speed of execution and/or hardware resources), it is often most effective to provide a sequential executable that provides equivalent functionality to the current functional specification.
A very general form of concurrent programming is the specification of a concurrent control flow graph. A very general form of sequential programming is the specification of a sequential control flow graph. It is therefore desirable to have efficient procedures for converting a concurrent control flow graph into a sequential control flow graph.
A control flow graph (or CFG) is essentially a kind of flow chart, as that term is conventionally understood, that depicts the flow of control of a program as edges connecting nodes (where the nodes represent operations to be performed). Since these edges define possible flows of control, they may be referred to as “control edges.” The nodes of a CFG comprise plain and conditional nodes, each with an expression. When control reaches a node, the node's expression is evaluated and control flows along one or more edges leaving the node. A plain node has a single outgoing edge and its expression is usually an assignment. Control leaves a conditional node along the edge whose label matches the value of the expression.
In a sequential CFG (or SCFG) there is only a single path of execution (or thread) through the CFG.
A concurrent CFG (or CCFG) is a CFG which also includes fork and join nodes, each of these nodes also having an expression. Fork and join nodes start and collect groups of parallel threads. Control flows out all edges leaving a fork, starting a group of threads that will wait at a matching join node before continuing. Fork and join nodes may nest, but control may not pass between threads. Specifically, all paths from a particular fork must meet for a first time at a unique join.
In addition to specifying a concurrent program in terms of a CCFG, it is often desirable to express the concurrent program in a higher-level programming language which is then translated into a CCFG. Alternatively, it may be desirable to express the concurrent program in terms of a graphical language that is then translated into a CCFG.
An example of a suitable concurrent programming language for specifying the functionality of an embedded computer system is the Esterel language. The Esterel language is described in Berry and Gonthier's “The Esterel Synchronous Programming Language: Design, Semantics and Implementation,” Science of Computer Programming, volume 19 number 2 pages 87–152, November 1992 (Elsevier Science, Amsterdam, The Netherlands), which is herein incorporated by reference. This paper formally describes the semantics of the language.
Esterel has the control constructs of an imperative language like C, but includes concurrency, preemption, and a synchronous model of time like that used in synchronous digital circuits. In each clock cycle, an Esterel program restarts, reads its inputs, and determines its reaction.
FIG. 1 shows a simple Esterel program with two concurrent threads. The first thread waits for the START signal and emits REQUEST. If it receives GRANT in the same cycle, it emits the GOT signal. In alternating cycles, the other thread emits GRANT in response to REQUEST. The threads restart when the RESET signal appears because of the abort-when RESET construct inside the outer loop.
The translation of Esterel into the CCFG may be accomplished in a variety of ways. A particular translation of Esterel into a CCFG is presented herein by pairing Esterel statements with their corresponding implementation as a program fragment of “concurrent C.” Concurrent C is a form of pseudo-code which is utilized in this patent for expository purposes. Concurrent C is essentially the same as standard C, with the addition statements that perform the fork and join functions. The translation of concurrent C into a CCFG can be accomplished by a variety of known methods. In this patent, Esterel statements are paired with their corresponding concurrent C program fragment, rather than with their corresponding CCFG fragment, for expository convenience.
FIGS. 2A through 2D depict the translations of the Esterel statements, that do not affect time, into concurrent C code. For each of these Figures, the Esterel statement is on the left and the concurrent C code translation is on the right.
The “exit” statement of Esterel throws an exception that can be caught by a surrounding “trap T in . . . handle T do.” This only happens after all threads in the same group are done for the cycle. To handle this, each thread sets an exit level when it stops at the end of a cycle. This level indicates termination (level 0), pausing (level 1), or an exception (levels 2 and higher). Exceptions take precedence over pauses, so a group of threads responds only to the highest level.
A “pause” statement resumes in the next cycle. A pause statement is shown on the left side of FIG. 3A, with the right side depicting its translation into concurrent C. The operation of this concurrent C is as follows. The code sets its threads state to “k,” making the “switch” statement surrounding the thread send control to the “case” label next cycle. Raising the exit level to 1 indicates this thread has paused. The branch to “join” stops the thread for the cycle.
The “await” statement is similar to “pause,” but it also pauses in later cycles until its signal is present. An await statement is shown on the left side of FIG. 3B, with the right side depicting its translation into concurrent C.
Esterel's preemption statements, such as “abort,” introduce the equivalent of nested “switch” statements in concurrent C. This is shown in FIG. 3C where an Esterel abort statement is shown on the left and is paired with its translation into concurrent C on the right side. In the first cycle, “abort” just runs its body. It restarts its body in later cycles only if the aborting signal is absent.
The Esterel “suspend” statement runs its body in the first cycle and pauses in later cycles when the suspending signal is absent, leaving its thread's state unchanged. This operation of suspend is depicted in FIG. 3D where an Esterel suspend statement is shown on the left and is paired with its translation into concurrent C on the right side.
The Esterel “signal” statement creates a new, absent copy of its signal. This operation of signal is depicted in FIG. 3E where an Esterel signal statement is shown on the left and is paired with its translation into concurrent C on the right side.
The Esterel “exit” statement raises its process's exit level to two or more depending on the exception. Since this terminates the thread and its process, there is no need to set the thread's state. This operation of exit is depicted in FIG. 3F where an Esterel exit statement is shown on the left and is paired with its translation into concurrent C on the right side.
In Esterel, “parallel” and “trap” statements are intertwined. An example of this is shown on the left side of FIG. 3G. An implicit trap surrounds each group of parallel threads, and the body of a trap is considered a separate thread. The trap/parallel combination resets the exit level for the enclosed process, runs the threads within, and handles the exit level they return. In the concurrent C translation of FIG. 3G, the process terminates if the level is zero (the switch falls through), pauses at level one, and handles exceptions at levels two and higher.
Furthermore, the concurrent C translation of the right side of FIG. 3G implements the Esterel “parallel” and “trap” statements as follows. The threads have two entry points: one taken in the first cycle, the other taken in later cycles that use “switch” statements to restart the threads. The “fork” statement passes control to each of its labels. The “join” waits until all the threads branch to it before continuing. A terminated thread sets its state to zero so control will go to the case 0: labels when other threads in the process continue to run.
In addition to the above pairings, the translation of Esterel nested abort statements into an CCFG is accomplished according to the following procedure. The following procedure also applies to the simpler situation of sequenced pause statements.
At the beginning of each clock cycle, every running Esterel thread checks the signals that might abort running blocks before resuming where it paused in the last cycle. Each CCFG thread simulates this behavior by saving its state at the end of a cycle and resuming at the beginning of the next with “switch” statements.
Nested aborts in the Esterel program are handled with nested switches in the concurrent C code. A thread's aborts form a tree with a signal at each node and a pause or group of threads at each leaf. Restarting a thread at the beginning of a cycle requires checking for abortion signals along the path from the root to the leaf that had control at the end of the last cycle.
Each node of the tree is translated into an “if” that checks the aborting signal and a “switch” that sends control to a child. The encoding of a thread's states (which corresponds to the leaves of the preemption tree) simplifies the decision at each switch. The edges leaving each node are numbered 0, 1, 2, etc. and become the “case” labels. The sequence of edge labels from the root to a leaf becomes the encoding for the leaf. These labels are packed into a single machine word so each switch statement can extract them with a mask and a shift. FIG. 4 depicts an example that illustrates state encoding with nested aborts (and sequenced pauses) on the left in Esterel and the translation into state-encoded concurrent C on the right. Code that sets exit levels (explained above) is not shown in FIG. 4.